﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;

namespace CRFEncoder
{
    static class Utils
    {
        public const float eps = 1e-7f;

        static double[] logsumexp_array_2_13_step01 = {
		0.126928011043, 0.11551952318, 0.105083319769, 0.095545464598, 0.0868361521539, 0.0788897342925, 0.0716446919677, 0.0650435617766, 0.059032826288, 0.053562776218, 0.0485873515737, 0.0440639679386, 0.0399533331624, 0.0362192588707, 0.0328284704249, 0.0297504182726, 0.0269570930082, 0.0244228459338, 0.0221242164549, 0.0200397672604, 0.0181499279178, 0.0164368472529, 0.0148842546719, 0.013477330416, 0.0122025846077, 0.0110477448486, 0.0100016520557, 0.00905416416989, 0.00819606733827, 0.00741899414869, 0.00671534848912, 0.00607823660178, 0.00550140390966, 0.00497917720433, 0.00450641179925, 0.00407844327057, 0.00369104342695, 0.00334038017037, 0.00302298093083, 0.00273569937854, 0.00247568513773, 0.00224035624625, 0.00202737412384, 0.00183462083059, 0.00166017841405, 0.00150231015975, 0.00135944357526, 0.00123015495171, 0.00111315536046, 0.00100727795423, 0.000911466453774, 0.000824764711326, 0.000746307251828, 0.000675310701585, 0.000611066022253, 0.000552931475361, 0.000500326249386, 0.000452724687599, 0.000409651060525, 0.000370674832054, 0.000335406372896, 0.000303493079395, 0.000274615859585, 0.000248485951917, 0.000224842045312, 0.000203447672129, 0.000184088848276, 0.000166571937112, 0.000150721716007, 0.000136379626358, 0.000123402189723, 0.000111659574328, 0.0001010342977, 9.14200525379e-05, 8.27206441097e-05, 7.48490286292e-05, 6.77264430034e-05, 6.12816172966e-05, 5.54500620491e-05, 5.0173423349e-05, 4.53988992169e-05, 4.10787114834e-05, 3.71696278849e-05, 3.36325296059e-05, 3.04320199499e-05, 2.75360702288e-05, 2.49156993328e-05, 2.25446837799e-05, 2.03992953441e-05, 1.84580636446e-05, 1.67015613183e-05, 1.51122096299e-05, 1.36741025747e-05, 1.23728477178e-05, 1.11954221735e-05, 1.01300422896e-05, 9.16604572783e-06, 8.29378476726e-06, 7.50452975604e-06, 6.79038175264e-06, 6.14419347775e-06, 5.55949778751e-06, 5.03044295448e-06, 4.55173410396e-06, 4.11858022627e-06, 3.7266462281e-06, 3.37200954892e-06, 3.05112090331e-06, 2.76076876118e-06, 2.49804720581e-06
	};

        static double[] logsumexp_array_0_2_step001 = {
		0.69314718056, 0.688159680508, 0.683197179727, 0.678259676341, 0.673347167228, 0.668459648013, 0.663597113076, 0.658759555549, 0.653946967318, 0.649159339026, 0.644396660074, 0.639658918622, 0.634946101596, 0.630258194682, 0.625595182337, 0.62095704779, 0.616343773041, 0.611755338871, 0.607191724841, 0.602652909299, 0.598138869382, 0.593649581022, 0.589185018951, 0.584745156704, 0.580329966626, 0.575939419879, 0.571573486442, 0.567232135122, 0.56291533356, 0.558623048234, 0.554355244469, 0.550111886439, 0.54589293718, 0.541698358594, 0.537528111455, 0.533382155419, 0.52926044903, 0.525162949731, 0.521089613866, 0.517040396695, 0.5130152524, 0.509014134091, 0.505036993818, 0.50108378258, 0.497154450332, 0.493248945997, 0.489367217474, 0.485509211647, 0.481674874396, 0.477864150606, 0.47407698418, 0.470313318045, 0.466573094165, 0.46285625355, 0.459162736271, 0.455492481463, 0.451845427344, 0.448221511221, 0.444620669502, 0.441042837708, 0.437487950486, 0.433955941617, 0.430446744029, 0.426960289812, 0.423496510223, 0.420055335703, 0.416636695888, 0.413240519622, 0.409866734964, 0.406515269207, 0.403186048885, 0.399878999791, 0.39659404698, 0.393331114793, 0.390090126859, 0.386871006115, 0.383673674814, 0.380498054542, 0.377344066223, 0.374211630142, 0.371100665948, 0.368011092673, 0.364942828742, 0.361895791988, 0.35886989966, 0.355865068442, 0.352881214461, 0.349918253302, 0.346976100019, 0.344054669151, 0.341153874732, 0.338273630304, 0.33541384893, 0.332574443207, 0.32975532528, 0.326956406851, 0.324177599195, 0.321418813172, 0.318679959237, 0.315960947457, 0.313261687518, 0.310582088744, 0.307922060102, 0.30528151022, 0.302660347398, 0.300058479618, 0.297475814558, 0.294912259605, 0.292367721864, 0.289842108174, 0.287335325115, 0.284847279025, 0.282377876008, 0.279927021946, 0.277494622514, 0.275080583186, 0.272684809253, 0.270307205826, 0.267947677858, 0.265606130143, 0.263282467338, 0.260976593967, 0.258688414435, 0.256417833037, 0.254164753971, 0.251929081345, 0.249710719193, 0.247509571479, 0.245325542113, 0.243158534955, 0.241008453833, 0.238875202546, 0.236758684876, 0.234658804601, 0.2325754655, 0.230508571364, 0.228458026006, 0.226423733273, 0.224405597047, 0.222403521265, 0.220417409918, 0.218447167068, 0.21649269685, 0.214553903485, 0.212630691286, 0.21072296467, 0.20883062816, 0.2069535864, 0.205091744159, 0.203245006338, 0.201413277983, 0.199596464286, 0.197794470597, 0.19600720243, 0.194234565472, 0.192476465587, 0.190732808824, 0.189003501427, 0.187288449837, 0.185587560704, 0.183900740888, 0.182227897471, 0.180568937757, 0.178923769285, 0.177292299831, 0.175674437415, 0.174070090305, 0.172479167028, 0.170901576368, 0.169337227379, 0.167786029386, 0.166247891992, 0.16472272508, 0.163210438824, 0.16171094369, 0.160224150438, 0.158749970135, 0.157288314151, 0.155839094169, 0.154402222188, 0.152977610526, 0.151565171825, 0.150164819057, 0.148776465523, 0.147400024863, 0.146035411055, 0.144682538421, 0.14334132163, 0.142011675702, 0.140693516009, 0.139386758283, 0.138091318613, 0.136807113452, 0.135534059621, 0.134272074308, 0.133021075073, 0.131780979851, 0.130551706955, 0.129333175076, 0.128125303286
	};
        public const int MINUS_LOG_EPSILON = 13;

        public static float logsumexp(float x, float y, bool flg)
        {
            if (flg) return y;  // init mode

            float vmin = (x < y) ? x : y;
            float vmax = (x > y) ? x : y;
            if (vmax > vmin + MINUS_LOG_EPSILON)
            {
                return vmax;
            }
            else
            {
                double v_diff = vmax - vmin;
                if (v_diff < 13 && v_diff >= 2)
                {
                    return vmax + (float)logsumexp_array_2_13_step01[(int)((v_diff - 2) * 10)];
                }
                else if (v_diff < 2)
                {
                    return vmax + (float)logsumexp_array_0_2_step001[(int)(v_diff * 100)];
                }
                else
                {
                    return vmax;
                }
            }

        }

        static public void calcAlpha(int m, int n, ref Node[,] node, ref Path[] pathList)
        {
            node[m, n].alpha = 0.0f;
            for (int i = 0; i < node[m, n].lpath_cnt; i++)
            {
                int lpath_id = node[m, n].lpath_id[i];
                Node lnode = node[pathList[lpath_id].lnode_x, pathList[lpath_id].lnode_y];
                node[m, n].alpha = Utils.logsumexp(node[m, n].alpha, pathList[lpath_id].cost + lnode.alpha, (i == 0));
            }
            node[m, n].alpha += node[m, n].cost;
        }

        static public void calcBeta(int m, int n, ref Node[,] node, ref Path[] pathList)
        {
            node[m, n].beta = 0.0f;
            for (int i = 0; i < node[m, n].rpath_cnt; i++)
            {
                int rpath_id = node[m, n].rpath_id[i];
                Node rnode = node[pathList[rpath_id].rnode_x, pathList[rpath_id].rnode_y];
                node[m, n].beta = Utils.logsumexp(node[m, n].beta, pathList[rpath_id].cost + rnode.beta, (i == 0));
            }
            node[m, n].beta += node[m, n].cost;
        }

        static public void calcExpectation(int x, int y, ref BigArray<float> expected, float Z, int size, ref List<int[]> feature_cache, ref Node[,] node, ref Path[] pathList)
        {
            Node n = node[x, y];
            float c = (float)Math.Exp(n.alpha + n.beta - n.cost - Z);
            int[] f = feature_cache[n.fid];
            for (int i = 0; i < f.Length; ++i)
            {
                expected[f[i] + y + 1] += c;
            }

            for (int i = 0; i < n.lpath_cnt; i++)
            {
                Utils.calcExpectation(pathList[n.lpath_id[i]], ref expected, Z, size, ref feature_cache, ref node);
            }
        }

        static public void calcExpectation(Path p, ref BigArray<float> expected, float Z, int size, ref List<int[]> feature_cache, ref Node[,] node)
        {
            Node lnode = node[p.lnode_x, p.lnode_y];
            Node rnode = node[p.rnode_x, p.rnode_y];
            float c = (float)Math.Exp(lnode.alpha + p.cost + rnode.beta - Z);
            int[] f = feature_cache[p.fid];
            int offset = p.lnode_y * size + p.rnode_y + 1;
            for (int i = 0; i < f.Length; ++i)
            {
                expected[f[i] + offset] += c;
            }
        }

        static object ll = new object();
        static public float ddot_(long size, BigArray<float> dx, long dx_idx, BigArray<float> dy, long dy_idx)
        {
            float ret = 0.0f;
            Parallel.For<float>(0, size, () => 0, (i, loop, subtotal) =>
            {
                subtotal += dx[i + dx_idx] * dy[i + dy_idx];
                return subtotal;
            },
            (subtotal) => // Accumulator
            {
                lock (ll)
                {
                    ret += subtotal;
                }
            });

            return ret;
        }
    }
}
